#define _CRT_SECURE_NO_WARNINGS 1

#include"BinaryTree.h"

void CreateBTree(BTNode** Tree, char* str)
{
	BTNode* Stack[MaxSize] = { 0 };
	BTNode* root = NULL;
	int top = -1, ret = 0, i = 0;
	char ch = str[i];
	while (ch != '\0')
	{
		switch (ch)
		{
		case'(':
			top++;
			Stack[top] = root;
			ret = 1;
			break;
		case')':
			top--;
			break;
		case',':
			ret = 2;
			break;
		default:
 			root = (BTNode*)malloc(sizeof(BTNode));
			if (root == NULL)
			{
				perror("root malloc:");
				return;
			}
			root->val = ch;
			root->leftchild = root->rightchild = NULL;
			if (*Tree == NULL)
			{
				*Tree = root;
			}
			else
			{
				switch (ret)
				{
				case 1:
					Stack[top]->leftchild = root;
					break;
				case 2:
					Stack[top]->rightchild = root;
					break;
				}
			}
		}
		++i;
		ch = str[i];
	}
}

void DispBTree(BTNode* root)
{
	if (root != NULL)
	{
		printf("%c", root->val);
		if (root->leftchild != NULL || root->rightchild != NULL)
		{
			printf("(");
			DispBTree(root->leftchild);
			if (root->rightchild != NULL)
			{
				printf(",");
			}
			DispBTree(root->rightchild);
			printf(")");
		}
	}
}

BTNode* FindNode(BTNode* root, ElemType val)
{
	BTNode* ret;
	if (root == NULL)
	{
		return NULL;
	}
	else if (root->val == val)
	{
		return root;
	}
	else
	{
		ret = FindNode(root->leftchild, val);
		if (ret != NULL)
		{
			return ret;
		}
		else
		{
			return FindNode(root->rightchild, val);
		}
	}
}

BTNode* LChildNode(BTNode* root)
{
	return root->leftchild;
}

BTNode* RChildNode(BTNode* root)
{
	return root->rightchild;
}

int BTHeight(BTNode* root)
{
	int lHeight = 0;
	int rHeight = 0;
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		lHeight = BTHeight(root->leftchild);
		rHeight = BTHeight(root->rightchild);
		return lHeight > rHeight ? lHeight + 1 : rHeight + 1;
	}
}

void DestroyBTree(BTNode** root)
{
	if (*root != NULL)
	{
		DestroyBTree(&((*root)->leftchild));
		DestroyBTree(&((*root)->rightchild));
		free(*root);
	}
}